We consider the problem of optimally designing a body wireless sensornetwork, while taking into account the uncertainty of data generation ofbiosensors. Since the related min-max robustness Integer Linear Programming(ILP) problem can be difficult to solve even for state-of-the-art commercialoptimization solvers, we propose an original heuristic for its solution. Theheuristic combines deterministic and probabilistic variable fixing strategies,guided by the information coming from strengthened linear relaxations of theILP robust model, and includes a very large neighborhood search for reparationand improvement of generated solutions, formulated as an ILP problem solvedexactly. Computational tests on realistic instances show that our heuristicfinds solutions of much higher quality than a state-of-the-art solver and thanan effective benchmark heuristic.
展开▼